package com.sheng.leetcode.year2023.month08.day18;

import org.junit.Test;

/**
 * @author by ls
 * @date 2023/8/18
 * <p>
 * 1388. 3n 块披萨<p>
 * <p>
 * 给你一个披萨，它由 3n 块不同大小的部分组成，现在你和你的朋友们需要按照如下规则来分披萨：<p>
 * 你挑选 任意 一块披萨。<p>
 * Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。<p>
 * Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。<p>
 * 重复上述过程直到没有披萨剩下。<p>
 * 每一块披萨的大小按顺时针方向由循环数组 slices 表示。<p>
 * 请你返回你可以获得的披萨大小总和的最大值。<p>
 * <p>
 * 示例 1：<p>
 * 输入：slices = [1,2,3,4,5,6]<p>
 * 输出：10<p>
 * 解释：选择大小为 4 的披萨，Alice 和 Bob 分别挑选大小为 3 和 5 的披萨。然后你选择大小为 6 的披萨，<p>
 * Alice 和 Bob 分别挑选大小为 2 和 1 的披萨。你获得的披萨总大小为 4 + 6 = 10 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：slices = [8,9,8,6,1,1]<p>
 * 输出：16<p>
 * 解释：两轮都选大小为 8 的披萨。如果你选择大小为 9 的披萨，你的朋友们就会选择大小为 8 的披萨，这种情况下你的总和不是最大的。<p>
 * <p>
 * 提示：<p>
 * 1 <= slices.length <= 500<p>
 * slices.length % 3 == 0<p>
 * 1 <= slices[i] <= 1000<p>
 */
public class LeetCode1388 {

    @Test
    public void test01() {
//        int[] slices = {1, 2, 3, 4, 5, 6};
        int[] slices = {8, 9, 8, 6, 1, 1};
        System.out.println(new Solution().maxSizeSlices(slices));
    }
}

class Solution {

    int n;

    public int maxSizeSlices(int[] slices) {
        // 考虑第一块不考虑最后一块和考虑最后一块不考虑第一块，2者最大
        n = slices.length;
        return Math.max(helper(slices, 0, n - 1), helper(slices, 1, n));
    }

    /**
     * 从长度为 3N 的数组中取出 N 个不相邻的数使和最大
     */
    public int helper(int[] slices, int p, int q) {
        // dp[i][j] 考虑前 i + 1 个元素，取出不相邻的 j + 1 个元素的最大值
        int[][] dp = new int[n][n / 3];
        int max = slices[p];
        for (int i = p; i < q; i++) {
            // 初始化，取出一个元素即到 i 为止的最大值
            max = Math.max(max, slices[i]);
            dp[i][0] = max;
        }
        for (int j = 1; j < n / 3; j++) {
            for (int i = j + 1; i < q; i++) {
                // 取或不取当前元素
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 2][j - 1] + slices[i]);
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }
}
